The fundamental ideas concerning computation and recursion naturally find their place at the interface between logic and theoretical computer science. The contributions in this book, by leaders in the field, provide a picture of current ideas and methods in the ongoing investigations into the pure mathematical foundations of computability theory. The topics range over computable functions, enumerable sets, degree structures, complexity, subrecursiveness, domains and inductive inference. A number of the articles contain introductory and background material which it is hoped will (...) make this volume an invaluable resource for specialists and non-specialists alike. (shrink)

Let p be a set. A function φ is uniformly σ 1 (p) in every admissible set if there is a σ 1 formula φ in the parameter p so that φ defines φ in every σ 1 -admissible set which includes p. A theorem of Van de Wiele states that if φ is a total function from sets to sets then φ is uniformly σ 1R in every admissible set if anly only if it is E-recursive. A function is (...) ES p -recursive if it can be generated from the schemes for E-recursion together with a selection scheme over the transitive closure of p. The selection scheme is exactly what is needed to insure that the ES p - recursively enumerable predicates are closed under existential quantification over the transitive closure of p. Two theorems are established: a) If the transitive closure of p is countable than a total function on sets is ES p -recursive if and only if it is uniformly σ 1 (p) in every admissible set. b) For any p, if φ is a function on the ordinal numbers then φ is ES p -recursive if and only if it is uniformly ∑ 1 (p) in every admissible set. (shrink)